/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
const DIRS = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0],
]; // 右下左上

var spiralOrder = function (matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const ans = Array(m * n);
  let i = 0;
  let j = 0;
  let di = 0;

  for (let k = 0; k < m * n; k++) {
    // 一共走 mn 步
    ans[k] = matrix[i][j];
    matrix[i][j] = Infinity; // 标记，表示已经访问过（已经加入答案）
    const x = i + DIRS[di][0];
    const y = j + DIRS[di][1]; // 下一步的位置
    // 如果 (x, y) 出界或者已经访问过
    if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] === Infinity) {
      di = (di + 1) % 4; // 右转 90°
    }
    i += DIRS[di][0];
    j += DIRS[di][1]; // 走一步
  }
  return ans;
};
